package com.black.cat.algorithm.link;

/**
 * @description:
 * @version: 1.0
 * @create：2023/2/1 14:32
 * @author：blackcat
 */
public class LinkedList<E> implements List<E> {


    /**
     * 链表长度
     */
    private int size;


    /**
     * 记录链表首节点
     */
    private Node<E> first;


    /**
     * 记录链表尾节点
     */
    private Node<E> last;

    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    private void linkLast(E e) {
        //获取当前最后一个节点
        Node l = last;
        //创建新的最后节点
        Node newNode = new Node(l, e, null);

        //当前最后的节点为null，没有添加过节点，首节点为新节点，此时尾节点都是新节点
        if (l == null) {
            first = newNode;
        } else {
            //当前最后的节点不为null,当前的最后节点的下一个节点为新节点
            l.next = newNode;
        }
        //修改最后的节点为当前最新的节点
        last = newNode;
        //长度+1
        size++;
    }

    @Override
    public boolean addFirst(E e) {
        linkFirst(e);
        return true;
    }

    private void linkFirst(E e) {
        //获取当前首节点
        Node<E> f = this.first;

        //创建新的首节点
        Node newNode = new Node(null, e, first);

        //当前当前首节点为null，没有添加过节点，尾节点为新节点，此时首位节点都是新节点
        if (f == null) {
            last = newNode;
        } else {
            //当前首节点的前一个节点为新节点
            f.pre = newNode;
        }
        //修改首节点为当前最新的节点
        first = newNode;
        //长度+1
        size++;
    }

    @Override
    public boolean addLast(E e) {
        linkLast(e);
        return true;
    }


    @Override
    public boolean remove(Object o) {
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (x.item.equals(o)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    private void unlink(Node<E> node) {
        Node pre = node.pre;
        E element = node.item;
        Node next = node.next;

        node.item = null;
        //前一个节点是null，说明当前节点为fist
        if (pre == null) {
            //首节点修改为next,当前节点删除
            first = next;
        } else {
            pre.next = next;
            node.pre = null;
        }
        //后一个节点是null，说明当前节点为last
        if (next == null) {
            //修改尾节点为pre
            last = pre;
        } else {
            next.pre = pre;
            node.next = null;
        }
        size--;
    }

    /**
     * 2分法获取
     *
     * @param index
     * @return
     */
    @Override
    public E get(int index) {
        return null;
    }


    /**
     * 双链表结构
     */
     class Node<E> {

        private E item;

        private Node<E> pre;

        private Node<E> next;


        public Node(Node<E> pre, E item, Node<E> next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
}
